package dfs;
/*
* 5. 最长回文子串
*
* 中心扩散法
*
* 分奇数中心与偶数中心情况
* */
public class LongestPalindrome5 {
    public String longestPalindrome(String s){
        if(s.length()==1){
            return s;
        }
        int start=0;
        int end=0;
        for(int i=0;i<s.length();i++){
            int a=expandAroundCenter(s,i,i);
            int b=expandAroundCenter(s,i,i+1);
            int len=Math.max(a,b);
            if(len>end-start){
                start=i-(len-1)/2;
                end=i+len/2;
            }
        }
        return s.substring(start,end+1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
            --left;
            ++right;
        }
        return right-left-1;
    }
}